import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 涛
 * Date: 2023-10-09
 * Time: 10:06
 */
public class TestHeap {
    public int[] elem;//存放堆的数组
    public int usedSize;//堆的大小
    public TestHeap() {
        this.elem = new int[10];
    }
    //初始化elem的方法,层序遍历的二叉树
    public void initElem(int[] array) {
        for(int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            usedSize++;
        }
    }

    /**
     * 创建大根堆的代码
     */
    public void createHeap() {
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
            //每次都向下调整，父亲节点和孩子节点比较，孩子节点比父亲节点大就交换
            siftDown(parent, usedSize);
        }
    }

    /**
     * 向下调整
     * @param parent
     * @param len
     */
    private void siftDown(int parent, int len) {
        //记录孩子节点的下标
        int child = 2 * parent + 1;
        //至少有左孩子
        while(child < len) {
            //先把比较左右孩子，看谁大，再和父亲节点比较
            if(child + 1 < len && elem[child] < elem[child + 1]) {
                //child下标记录最大的孩子
                child++;
            }
            //走到这里，child下标一定是孩子中最大的一个,比较parent和child下标元素
            if(elem[child] > elem[parent]) {
                swap(child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }
    public void  swap(int i, int j) {
        int tmp = 0;
        tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }
    //插入元素
    public void push(int val) {
        //扩容
        if(isFull()){
            this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
        }
        //插入在堆的最后
        this.elem[usedSize] = val;
        //向上调整
        siftUp(usedSize);
        usedSize++;//调整完后再+1
    }
    //向上调整
    public void siftUp(int child) {
        int parent = (child - 1) / 2;
        while (child > 0) {
            if(elem[child] > elem[parent]) {
                swap(child, parent);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }
    public int pop() {
        if(empty()) {
            return -1;
        }
        int oldVal = elem[0];
        swap(0, usedSize - 1);
        usedSize--;
        siftDown(0, usedSize);
        return oldVal;
    }
    //扩容
    public boolean isFull() {
        return this.elem.length == usedSize;
    }
    //判断堆是不是空的
    public boolean empty() {
        return usedSize == 0;
    }
}
